力扣151 |
您所在的位置:网站首页 › 翻转字符串里的单词 java › 力扣151 |
Hello大家好,这是一道在字符串题目中有关双指针解法的题目,属于比较经典又有操作性和复杂度的例题,因而拿出来做讲解,详细介绍送给大家:gift_heart: @TOC 一、原题描述原题传送门给你一个字符串 s ,请你反转字符串中 单词 的顺序。 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。 注意:输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中,单词间应当仅用单个空格分隔,且不包含任何额外的空格。 示例 1: 输入:s = "the sky is blue" 输出:"blue is sky the"示例 2: 输入:s = " hello world " 输出:"world hello" 解释:反转后的字符串中不能存在前导空格和尾随空格。示例 3: 输入:s = "a good example" 输出:"example good a" 解释:如果两个单词间有多余的空格,反转后的字符串需要将单词间的空格减少到仅有一个。二、思路分析1、题型引入之前有做过一道题叫做力扣344.反转字符串,也是利用双指针的写法对一个字符串进行操作,题目的思路就是使用双指针不断地从两端向中间移动,然后依次互换两头的字符,因为只需要颠倒两头的字符,因为当两个双指针移动到中间时,即交换完毕代码很简洁,知道思路有了,双指针的代码并不难写,C/C++代码如下:ear_of_rice: class Solution { public: void reverseString(vector& s) { int left = 0; int right = s.size() - 1; while(left < s.size()/2) swap(s[left++],s[right--]); } };2、思路分析通过上一题字符串的翻转的引入,相信大家对双指针如何在字符串中进行使用已经有了一个初步的了解,但是本题却没有那么容易,==不然我也不会拿出来作为经典例题讲解==首先看题目本身,给到一个字符串s,要返回的是字符串中单词的顺序,这里要注意,不是和上一题一样将一个子串做颠倒,而是整体性地进行一个翻转,这就需要我们去分步骤讨论和分析。还有一点要注意的是给出的目标串可能子串单词不一定只会有一个空格,也可能会有多个空格,这是我在调试运行的时候观测到的一点,而且这个s串可能还具有前导空格和尾部空格,这些都需要我们去考虑到,怎么样,是不是感觉一下子又要头脑风暴了:ocean:好,我们来大体地说一下整体的这个思路**①去除给出的目标串中多余的空格 ②将整个字符串做一个反转 ③逐个去将其中的子串单词一一翻转 ④完成单词的翻转** 想知道如何实现这几步吗,那就听我娓娓道来:mag:三、代码详解1、分步骤解析(1)移除给出字符串中的多余空格(Wonderful)首先就是第一步,移除给出字符串中的多余空格,这是第一步也是最关键的一步:key:因为只有在没有多余其他空格的干扰下才可以做整体翻转和局部翻转的可能【题外话】在力扣中这个题目中并给出这个空间复杂度的限制,这样就可以自己再开辟一个字符串做放置移位操作。而且随着现在字符串库函数的越加丰富,对于字符串的操作几乎不用自己思考,只需要调用一下API即可,所以大家都调侃自己时API调用工程师,确实,有些API在开发的时候是可以给我们带来便利,但是在刷题的过程中,我们看到一个操作就立马想到用API去解决,而且这道题的核心代码用API可直接解决,那就失去了刷题的意义,像这题你完全可以用Java中String类的split(),去分割单词,然后定义一个新的string字符串,最后再把单词倒序相加,你要这样做那这就是道水题,没有任何意义好的,言归正传,插了一些小话题,我们规定空间复杂度就只能是O(1),那么你就不可以再去使用辅助空间了,只能在原字符串中下功夫,这就可以想到我们的双指针解法了,还记得吗,我在力扣27 - 移除元素【双指针】中说到如何使用双指针循环交替换位去做消除元素的操作,这里其实也是一样的,那一题是消除元素,那这一题就是把元素换成空格而已但是有些小伙伴很单纯,就是用一个for循环去遍历字符串s,然后遇到空格就用erase()删除一下。哈哈,确实,这就是很直白的写法,我也可以给代码,从如下代码可以看出,我是将移除空格分为了三个部分,分别是**①移除字符串当中的多余空格 ②移除前导空格 ③移除尾随空格**但是你以为这只是O(n)的时间复杂度吗,不,==erase()这个API的底层实现就已经是O(n)==,然后外面在用一个for循环去遍历字符串,按就是O(n^2^)的时间复杂度,虽然是很清晰地分步骤解决了问题,但是却无故中增加了时间复杂度,而你自己可能还不知道void removeExtraspaces(string& s) { //移除字符串当中的多余空格 for(int i = s.size() - 1;i > 0; --i) { if(s[i] == s[i - 1] && s[i] == ' ') s.erase(s.begin() + i); } //移除前导空格 if(s.size() > 0 && s[0] == ' ') s.erase(s.begin()); //移除尾随空格 if(s.size() > 0 && s[s.size() - 1] == ' ') s.erase(s.begin() + s.size() - 1); }Ok,不多讲,我们的重点在于双指针,如何用双指针去除空格呢,上面说了,这就和移除元素是一个道理快指针fast:用来获取新数组中的元素,即不为空格的位置慢指针slow:获取新数组中需要更新的位置先行给出C++代码 void removeExtraSpaces(string& s) { int slow = 0; for(int fast = 0;fast < s.size(); ++fast) { if(s[fast] != ' ') //当快指针指向不为空格时,进行互相替换 { if(slow != 0) //解决每个单词之间的空格 s[slow++] = ' '; //若slow当前为0,则直接替换,为了解决前导空格 while(fast < s.size() && s[fast] != ' ') s[slow++] = s[fast++]; //指针元素互换,直到一个单词结束 } } s.resize(slow); //慢指针当前所指位置即为去空格后数组大小 }交替过程展示 还是一样,一张张分部图解手撕算法,为的是能让大家看清指针走的每一步,所以不要怕麻烦,跟着我一步一步来:walking:①首先,只有当fast快指针==指向不为空时==才做,交替,但一开始快指针指向首除,因此不进if(s[fast] != ' ')的判断,fast快指针直接后移
|
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |